package binarytree


type TreeNode struct{
	Val int
	Left,Right *TreeNode
}

// 有利于理解什么是否有返回值 什么时候没有

// 寻找是否有路径和为targetSum的
// 路径定义为根到叶子节点
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	var res bool
	var dfs func(node *TreeNode, pathSum int) bool
	// 不需要遍历整棵树  要有返回值及时返回
	dfs = func(node *TreeNode, pathSum int) bool{
		// 确定终止条件
		if node.Left==nil && node.Right==nil {
			// 到了叶子节点
			if pathSum + node.Val == targetSum {
				return true
			}
			return false
		}
		// 否则，常规递归操作
		var Lflag,Rflag bool
		if node.Left!=nil{
			Lflag = dfs(node.Left, pathSum+node.Val)  // 回溯的逻辑
		}
		if node.Right !=nil {
			Rflag = dfs(node.Right, pathSum+node.Val)
		}
		return Lflag || Rflag  // 有一个能找到就行
	}
	res = dfs(root, 0)
	return res
}